﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

//22. 括号生成

//数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
//简单的想法，生成所以的组合，然后判断有效的
//n=3，（（（））），全排列
class Sol22
{
    IList<string> res = new List<string>();
    public IList<string> GenerateParenthesis(int n)
    {


        //IList<char> path = new List<char>();

        string path = null;
        DFS(0, path, n,n);



        return res;
    }

    private void DFS(int curIndex, string path, int left,int right)
    {
        if (left == 0 && right == 0) {

            //res.Add(new string(path));
            res.Add(path);//这里path不用新建的原因是string每次改变会自动复制一份
            return;

        }


        //0肯定是左（
        if (left > 0) {//大于0，就加入，left使用完了（left==0)，就回溯

            DFS(0, path + '(', left - 1, right);
        }


        
        if(left<right)
        {
            DFS(0, path+')', left, right-1);
        }
       


    }
}

class Program22
{
    static void Main22(string[] args)
    {
        Sol22 sol= new Sol22();
        IList<string> res= sol.GenerateParenthesis(3);
        for(int i = 0; i < res.Count; i++)
        {
            Console.WriteLine(res[i]);
        }

    }
}
